/* 
	treapx.hpp
		cartesian tree by non-evident key.
		(c) marqueewinq, 2012
	implemented reverse
*/ 

int d32b(void)
{	return (rand() << 16) | rand(); }

struct treapx
{
	int y;                // key
	int count;            // size of subtree
	bool reversed;        // if true, children are reversed
	treapx *left, *right; // hrefs to children

	int id;               // value

	treapx (int _id, int _y = d32b()) 
	{
		id = _id, y = _y, reversed = false, count = 0, left = right = NULL;
	}
};
typedef treapx* ptreapx;

/* globals */
ptreapx root = NULL;

/* prototypes */
// basics of cartesian
void    split(int x, ptreapx cur, ptreapx &left, ptreapx &right, int add);
ptreapx merge(ptreapx left, ptreapx right);
bool    insert(int x);
bool    erase(int x);

// size euristics
int     count(ptreapx cur);
void    update(ptreapx &cur); 
void    push_rev(ptreapx cur);
void    reverse (int L, int R);
void    print(ptreapx cur, ostream &target);

/* implementation */

void split(int x, ptreapx cur, ptreapx &left, ptreapx &right, int add = 0)
	// splits treapx by key into (lesser) and (equal, greater) parts
{
	if (!cur)
	{
		left = right = NULL;
		return void();
	}
	
	push_rev(cur);
	int cur_key = add + count(cur->left);

	if (x <= cur_key)
		// cut is to the left
	{
		split(x, cur->left, left, cur->left, add);
		right = cur;
	}
	else
		// cut is to the right
	{
		split(x, cur->right, cur->right, right, add + count(cur->left) + 1);
		left = cur;
	}

	update(cur);
}

ptreapx merge(ptreapx left, ptreapx right)
	// merges two treapxs
{
	push_rev(left);
	push_rev(right);
	
	if (!left || !right)
		return (!right) ? left : right;

	ptreapx r = NULL;
	if (left->y < right->y)
		left->right = merge(left->right, right), r = left;
	else
		right->left = merge(left, right->left), r = right;
	
	update(r);
	return r;
}

bool insert(int x)
	// adds element to treapx; returns true if element was found
{
	ptreapx left, mid, right;
	bool existed = false;
	split(x, root, left, right);
	split(x + 1, right, mid, right);
	
	if (!mid)
		mid = new treapx(x), existed = true;;
	
	right = merge(mid, right);
	root = merge(left, right);

	update(root);
	return existed;
}

bool erase(int x)
	// erases element from treapx; returns true if element was found
{
	ptreapx left, mid, right;
	bool existed = false;
	split(x, root, left, right);
	split(x + 1, right, mid, right);
	
	if (!mid)
		existed = true;
	
	root = merge(left, right);

	update(root);
	return existed;
}

int count(ptreapx cur)
	// safe ->count field call
{
	return (!cur) ? 0 : cur->count;
}

void update(ptreapx &cur) 
	// updates ->count field
{
	if (cur)
		cur->count = 1 + count(cur->left) + count(cur->right);
}

void push_rev(ptreapx cur)
	// pushes reversal state to children
{
	if (cur && cur->reversed) 
	{
		cur->reversed = false;
		swap(cur->left, cur->right);
		if (cur->left)
			cur->left->reversed ^= true;
		if (cur->right)
			cur->right->reversed ^= true;
	}
}

void reverse(int L, int R)
	// reverses subarray from [left; right]
{
	ptreapx left, mid, right;

	split(L, root, left, right);
	split(R + 1 - L, right, mid, right); 

	if (mid)
		mid->reversed ^= true;

	right = merge(mid, right);
	root = merge(left, right);

	update(root);

	return void();
}

void print(ptreapx cur, ostream &target = cout)
	// prints treapx from left to right
{
	if (!cur)
		return void();
	push_rev(cur);

	print(cur->left, target);
	target << cur->id _;
	print(cur->right, target);
}

/* treapx ends */